package org.ala.linshen.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你两个 正 整数 n 和 x 。
 *
 * 请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。
 *
 * 由于答案可能非常大，请你将它对 109 + 7 取余后返回。
 *
 * 比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 10, x = 2
 * 输出：1
 * 解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
 * 这是唯一将 10 表达成不同整数 2 次方之和的方案。
 * 示例 2：
 *
 * 输入：n = 4, x = 1
 * 输出：2
 * 解释：我们可以将 n 按以下方案表示：
 * - n = 41 = 4 。
 * - n = 31 + 11 = 4 。
 *
 *
 * 提示：
 *
 * 1 <= n <= 300
 * 1 <= x <= 5
 *
 * @author ala
 * @date 2024-09-30 16:10
 */
public class Q2787 {

    public static void main(String[] args) {
        Q2787 q = new Q2787();

//        int n = 4, x = 1;
        int n = 2, x = 2;

        System.out.println(q.numberOfWays(n, x));
    }

    public int numberOfWays(int n, int x) {
        return V1(n, x);
    }
    static int MOD = (int)1e9 + 7;
    /**
     *  1）先计算待组合的数组 nums
     *      nums[0] = 1, nums[i] ^ x <= n
     *      问题转化为：从nums中取数，和为n的方案数
     *  2）dp[i]表示和为i的方案数
     *      dp[i] += dp[i - n]
     */
    protected int V1(int n, int x) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1 ; Math.pow(i, x) <= n ; i++) {
            nums.add(Double.valueOf(Math.pow(i, x)).intValue());
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int _n : nums) {
            for (int i = n ; i >= _n ; i--) {
                dp[i] = (dp[i] + dp[i - _n]) % MOD;
            }
        }
        return dp[n];
    }
}
